This invention relates to signal constellations for communication systems.
In communication systems using modems, for example, data is sent over a noise-affected channel by modulating a carrier in accordance with a series of signal points drawn from a constellation of available signal points. In a quadrature amplitude modulation (QAM) system, the constellation is two-dimensional. It is known that certain advantages can be achieved using higher-dimensional constellations to define the points to be transmitted.
An N-dimensional (N greater than 2) constellation C is a finite set of N-tuples (i.e., points each having N coordinates that together define a location in N-space). Important characteristics of such a constellation are the number .vertline.C.vertline. of its points, the minimum squared distance d.sub.min.sup.2 (C) between its points, and its average energy (or average Euclidean norm) P(C). For a given number of points, a figure of merit of a constellation when used for signaling is P(C)/d.sub.min.sup.2 (C) (the smaller, the better).
A general known method of constructing a good constellation (one with a small figure of merit) having a desired number of points is to choose a finite set of points from a so-called dense (tightly packed) N-dimensional lattice .LAMBDA., or from a coset of .LAMBDA. (i.e., a translated version of .LAMBDA.). The points may be selected by defining a region R in N-space that is just large enough to contain the desired number of points. The minimum squared distance d.sub.min.sup.2 (C) of the constellation is the minimum squared distance d.sub.min.sup.2 (.LAMBDA.) of the lattice .LAMBDA.; in general, to minimize the average energy P(C), the region R should resemble as nearly as possible an N-sphere centered on the origin.
Conway and Sloane, "A Fast Encoding Method for Lattice Codes and Quantizers," IEEE Trans. Inform. Theory, Vol. IT-29, pp. 820-824, 1983, incorporated herein by reference, propose the following way to define such a region R containing the desired number of points. Suppose that a given N-dimensional lattice .LAMBDA. has as a sublattice a scaled version M.LAMBDA. of the same lattice, where M is an integer scaling factor. That is, the sublattice is a subset of the points of the lattice selected so that the sublattice will be simply a larger scale version of the lattice. (Note that M.LAMBDA. and .LAMBDA. are lattices of the same type.) Then there are M.sup.N equivalence classes of points in the original lattice .LAMBDA. (or any coset of .LAMBDA.) modulo M.LAMBDA.. Note that two N-tuples are equivalent modulo M.LAMBDA. (and hence belong to an equivalence class) if their difference is a point in M.LAMBDA..
In accordance with Conway and Sloane, the so-called Voronoi region of the lattice M.LAMBDA. is the set of points in N-space that are at least as close to the origin as to any other lattice point in M.LAMBDA.. The interior of the Voronoi region may be defined as the set of points closer to the origin than to any other lattice point; the boundary of the Voronoi region is the set of points for which the origin is one of the closest points in the lattice, but for which there are other equally near lattice points. In general, the boundary is a closed surface in N-space, composed of a certain number of (N-1)-dimensional faces, which are portions of hyperplanes equidistant between two neighboring lattice points in M.LAMBDA.. (For example, the Voronoi region of an N-dimensional integer lattice Z.sup.N is an N-cube of side 1, whose faces are (N-1)-cubes of side 1. The intersections of the faces are figures of N-2 or fewer dimensions and have more than two nearest neighbors.)
Therefore, if .LAMBDA.+c is a coset of the original lattice (where c is a translation vector) that is chosen to have no points on the boundary of the Voronoi region of the scaled lattice M.LAMBDA., then the Voronoi region contains M.sup.N points of the coset .LAMBDA.+c, one from each equivalence class modulo M.LAMBDA., and the M.sup.N point Voronoi region may serve as a signal constellation called a Voronoi constellation (Conway and Sloane call it a Voronoi code). Such constellations are characterized by relatively small average energy and are shown by Conway and Sloane to have a straightforward implementation.
In my copending patent application, Signal Constellations, U.S. Ser. No. 062,497, filed June 12, 1987, assigned to the same assignee as this application, incorporated by reference, I disclosed using a constellation comprising points of a lattice .LAMBDA. (or a coset of .LAMBDA.) that lie within a Voronoi region of a sublattice .LAMBDA.' of .LAMBDA., where .LAMBDA.' is other than a scaled version of .LAMBDA.. There the constellation was based on a maximally biased selection of possibly fewer than all points in the Voronoi region, with some points possibly lying on a boundary of the Voronoi region.
Such an arrangement has a number of advantages. Constellations having a number .vertline..LAMBDA./.LAMBDA.'.vertline. of points other than simply the N.sup.th power of an integer (M.sup.N) may be constructed, where .vertline..LAMBDA./.LAMBDA.'.vertline. the order of the partition (index of the quotient group). Even if the original lattice .LAMBDA. is not a dense lattice (e.g., the N-dimensional integer lattice Z.sup.N), which may have advantages in certain coding schemes (e.g., coset codes), the Voronoi region of a dense lattice .LAMBDA.' may be used to define the boundary of the constellation, thus achieving the advantage of a quasi-spherical constellation. The method of mapping data words to Voronoi constellation points is straightforward to implement.
Lang et al., U.S. Pat. No. 4,538,284, issued Aug. 27, 1985, discloses two-dimensional symmetrical hexagonal constellations. For example, one such constellation contains 73 points including a 64-point suboptimal constellation (of the kind shown in Forney, et al., "Efficient Modulation for Band-Limited Channels", IEEE J. Select. Areas Commun., Vol SAC-2, pp. 632-647, 1984). Fifty-five of the points correspond to unique ones of the 64 possible data words; the remaining 18 points are grouped in pairs, each pair corresponding to one of the 9 remaining data words; when one of these data words occurs there is a further choice of one point of the corresponding pair, which can be used to support a secondary channel.